100. 相同的树

#leetcode/tree/traversal

100. 相同的树

Similar Question

leading to the advanced question

Solution Tips

572. 另一棵树的子树

方案一: 迭代 - 层次遍历

用迭代法的话，只需要维护一个栈，如果 nodeOne、nodeTwo 的值相同，则依次将 nodeOne->left，nodeTwo->left ，nodeOne->right，nodeTwo->right 入栈，然后下一次循环开始时，就判断栈顶的 nodeOne->right 和 nodeTwo->right 的值是否相同，相同的话，再把它们的左右孩子依次入栈，循环以上过程，直到碰到值不相等或者栈为空。【迭代法的算法流程可参考下面图解】

var isSameTree = function(p, q) {
    if (p === q) return true;

    if (p === null) return false;

    const o = [p];
    const t = [q];

    while (o.length > 0) {
        const m = o.shift();
        const n = t.shift();

        if (m === null && n === null) continue;
        // 仅有其中一个为 null
        if (m === null || n === null) return false;
        if (m.val !== n.val) return false;

        o.push(m.left)
        t.push(n.left)

        o.push(m.right)
        t.push(n.right)
    }

    return true;
};

方案二: 递归 - 深度优先遍历

判断两棵树是否相同，最直接的方法是用递归，假设两棵树的根节点分别是 nodeOne、nodeTwo，则它们相同的前提是 nodeOne 和 nodeTwo 的值相同，并且它们的左右子树也分别相同，显然对左右子树可以递归地调用原函数。

var isSameTree = function (p, q) {
    if (p === null && q === null) return true
    // 其中一个为空
    if (p === null || q === null) return false
    if (p.key === q.key) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
    return false
};